import java.util.Stack;
import java.util.EmptyStackException;
import java.util.Random;

/**
 * @author Jake Ellowitz
 *
 * Assignment 1, question 3, CS160
 *
 * Modified stack implementation with O(1) access to stack sum and stack
 * minimum. Tracking the sum is trivial. Tracking the minimum value is
 * trickier. It is done by holding a stack which is pushed only if the last
 * pushed value is a minimum, and popped if the last popped value is a
 * minimum. The top value will always be the absolute minimum, with all
 * subsequent values representing the subsequent minimum values in the
 * stack.
 *
 * Please forgive any conventions I am not abiding to, I am new to Java.
 */

public class JakeStack
{
	// The user should not be able to touch these directly
	private int sum;
	private Stack<Integer> stack;
	private Stack<Integer> min;

	/**
	 * Initialize the class by initiating the stacks we need, and zeroing the 
	 * sum. 
	 */
	public JakeStack ()
	{
		sum = 0;
		// We need two stacks: one for the minima and one for the entire stack
		stack = new Stack<Integer> ();
		min   = new Stack<Integer> ();
	}

	/**
	 * Append to the minimum stack, any stack errors would be identified in
	 * findMin (). Private because the user should not have direct access.
	 */
	private int minPush (int val)
	{
		// Can not be strictly less than--in the case of degenerate minima, if
		// one is removed the others should certainly remain minima!
		if (val <= findMin ())
			min.push (val);

		return val;
	}

	/**
	 * Pop from the minimum stack, stack errors would be identified in
	 * findMin (). Private because the user should not have direct access.
	 */
	private int minPop (int val)
	{
		if (val == findMin ())
			min.pop ();
		else if (val < min.peek ())
			System.out.println ("Error: minimum is not being tracked correctly.");

		return val;
	}

	//----------
	// BEGIN The primary stack operations, as specified.
	//----------
	
	/**
	 * Push the main stack, and also handle background tasks such as min and
	 * sum.
	 */
	public int push (int val)
	{
		stack.push (val);
		// Do the extra tracking as the additional stack requirements demand.
		sum += val;
		minPush (val);

		return val;
	}

	/**
	 * Pop the main stack, and also handle background tasks such as the min
	 * and sum.
	 */
	public int pop ()
	{
		int val;
		// Should the stack not be tracked correctly, we must handle cases in
		// which there are memory violations (i.e. accessing an empty stack)
		try
		{
			val = stack.pop ();
		}
		catch (EmptyStackException e)
		{
			System.out.println ("Attempted to pop an empty stack.");
			return 0;
		}
		// No exceptions, proceed as normal
		sum -= val;
		minPop (val);

		return val;
	}

	/**
	 * Take a look at the top of the stack; handles the case where the stack
	 * is empty.
	 */
	public int peek ()
	{
		try
		{
			return stack.peek ();
		}
		catch (EmptyStackException e)
		{
			System.out.println ("Attempted to peek at empty stack.");
		}

		return 0;
	}

	/**
	 * Return the sum of all of the values in the stack.
	 */
	public int sum ()
	{
		return sum;
	}

	/**
	 * Return the minimum value in the stack--this minimum value is tracked
	 * by an independent stack.
	 */
	public int findMin ()
	{
		// Should the stack not be tracked correctly, we must handle cases in
		// which there are memory violations (i.e. accessing an empty stack).
		// The private min handling routines use this function, thus it returns
		// a large value for an empty stack, signifying that any other integer 
		// would be the min.
		try
		{
			return min.peek ();
		}
		catch (EmptyStackException e)
		{
			// Largest positive integer.
			return 0x7FFFFFFF;
		}
	}

	//----------
	// END the primary stack operations
	//----------

	
	public static void main (String [] args)
	{
		int r;
		// Some random number seed. We generate numbers to push and pop.
		Random ran = new Random (1023);
		// Instatiate the class.
		JakeStack j = new JakeStack ();

		// Fill the stack with 5 values. Subsequently print the status.
		for (int i=0; i<5; ++i)
		{
			r = ran.nextInt (10);
			System.out.println ("Pushed: "+j.push (r)+", Top: "+j.peek ()+
				", Min: "+j.findMin ()+", Sum: "+j.sum ());
		}
		// Empty the stack, and attempt to pop and peek after stack is empty to
		// demonstrate that my code does not break under these circumstances.
		for (int i=0; i<6; ++i)
		{
			System.out.println ("Popped: "+j.pop ()+", Top: "+j.peek ()+
				", Min: "+j.findMin ()+", Sum: "+j.sum ());
		}
	}
}
